package com.example.demo.algorithm.lesson.basic.class1;

import static com.example.demo.algorithm.lesson.basic.class1.ArrayCompareHelper.newRandomArray;
import static com.example.demo.algorithm.lesson.basic.class1.ArrayCompareHelper.printArray;

/**
 * @author liweizhi
 * @date 2020/4/22 18:03
 * <p>
 * 简单来说,就是找任意一个"极小值"的位置
 * <p>
 * 一个无序不重复的数组,如果一个数比它两边的数都小,那么它就是局部最小值
 * 如果arr[0]<arr[1],那么arr[0]也是局部最小值;同理如果arr[n]<arr[n-1],则arr[n]满足条件
 * 现需要找到任意一个局部最小值的位置
 */
public class BSMinimalValue {
    public static int searchMinimalValue(int[] arr) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        if (arr.length == 1 || arr[0] < arr[1]) {
            return 0;
        }
        if (arr[arr.length - 1] < arr[arr.length - 2]) {
            return arr.length - 1;
        }

        int left = 1;
        int right = arr.length - 2;
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (arr[mid] > arr[mid - 1]) {
                right = mid - 1;
            } else if (arr[mid] > arr[mid + 1]) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return left;
    }

    public static void main(String[] args) {
//        int[] arr = {29, 11, 28, -12, 20, 45, 12, 15, -11, 23};
//        System.out.println(searchMinimalValue(arr));
        testIt();
    }

    private static void testIt() {
        int tryTimes = 30_0000;
        int size = 100;
        int max = 50;
        int min = -50;
        boolean succeed = true;
        for (int i = 0; i < tryTimes; i++) {
            int[] arr1 = newRandomArray(size, max, min);

            if (searchMinimalValue(arr1) == -1) {
                succeed = false;
                printArray(arr1);
                break;
            }
        }
        System.out.println(succeed ? "Yes" : "No");
    }
}
